package main

import "fmt"

func main() {
	arr := []int{4, 2, 22, 4, 5, 456, 2, 45, 45, 3, 34, 523, 5, 4, 0, 3, 1}
	fmt.Println(SelectSort(arr))
}

func Swap(arr []int, i, j int) []int {
	temp := arr[i]
	arr[i] = arr[j]
	arr[j] = temp
	return arr
}

/*
选择排序：
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

将假想墙放置在数字列表最左侧，墙的左侧为已排序子列表，右侧为未排序子列表；
找出（选择）未排序子列表中的最小（或最大）元素；
把选择的元素与未排序列表中第一个元素进行交换；
将假想墙向右移动一个位置；
反复执行 2 至 4 步操作，直至整个数字列表排序完成（需要 n - 1 轮）。
*/

func SelectSort(arr []int) []int {
	if len(arr) < 1 {
		return arr
	}

	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		arr = Swap(arr, i, minIndex)
	}

	return arr

}
